﻿namespace AdvancedTraining.Lesson19;

// LRU缓存实现：最近最少使用规则缓存
// 本题测试链接 : https://leetcode.cn/problems/lru-cache/
// 提交时把类名和构造方法名改成 : LRUCache
public class LRUCache(int capacity)
{
    private readonly MyCache<int, int> cache = new(capacity);

    public virtual int Get(int key)
    {
        int? ans = cache.Get(key);
        return ans == null ? -1 : ans.Value;
    }

    public virtual void Put(int key, int value)
    {
        cache.Set(key, value);
    }

    public class Node<TK, TV>
    {
        public TK key;
        public Node<TK, TV> last;
        public Node<TK, TV> next;
        public TV value;

        public Node(TK key, TV value)
        {
            this.key = key;
            this.value = value;
        }
    }

    public class NodeDoubleLinkedList<K, V>
    {
        private Node<K, V> head;
        private Node<K, V> tail;

        public NodeDoubleLinkedList()
        {
            head = null;
            tail = null;
        }

        // 现在来了一个新的node，请挂到尾巴上去
        public virtual void AddNode(Node<K, V> newNode)
        {
            if (newNode == null) return;
            if (head == null)
            {
                head = newNode;
                tail = newNode;
            }
            else
            {
                tail.next = newNode;
                newNode.last = tail;
                tail = newNode;
            }
        }

        // node 入参，一定保证！node在双向链表里！
        // node原始的位置，左右重新连好，然后把node分离出来
        // 挂到整个链表的尾巴上
        public virtual void MoveNodeToTail(Node<K, V> node)
        {
            if (tail == node) return;
            if (head == node)
            {
                head = node.next;
                head.last = null;
            }
            else
            {
                node.last.next = node.next;
                node.next.last = node.last;
            }

            node.last = tail;
            node.next = null;
            tail.next = node;
            tail = node;
        }

        public virtual Node<K, V> removeHead()
        {
            if (head == null) return null;
            var res = head;
            if (head == tail)
            {
                head = null;
                tail = null;
            }
            else
            {
                head = res.next;
                res.next = null;
                head.last = null;
            }

            return res;
        }
    }

    public class MyCache<K, V>
    {
        private readonly int capacity;
        private readonly Dictionary<K, Node<K, V>> keyNodeMap;
        private readonly NodeDoubleLinkedList<K, V> nodeList;

        public MyCache(int cap)
        {
            keyNodeMap = new Dictionary<K, Node<K, V>>();
            nodeList = new NodeDoubleLinkedList<K, V>();
            capacity = cap;
        }

        public virtual V Get(K key)
        {
            if (keyNodeMap.ContainsKey(key))
            {
                var res = keyNodeMap[key];
                nodeList.MoveNodeToTail(res);
                return res.value;
            }

            return default;
        }

        // Set(Key, Value)
        // 新增  更新value的操作
        public virtual void Set(K key, V value)
        {
            if (keyNodeMap.ContainsKey(key))
            {
                var node = keyNodeMap[key];
                node.value = value;
                nodeList.MoveNodeToTail(node);
            }
            else
            {
                // 新增！
                var newNode = new Node<K, V>(key, value);
                keyNodeMap[key] = newNode;
                nodeList.AddNode(newNode);
                if (keyNodeMap.Count == capacity + 1) RemoveMostUnusedCache();
            }
        }

        private void RemoveMostUnusedCache()
        {
            var removeNode = nodeList.removeHead();
            if (removeNode != null)
            {
                keyNodeMap.Remove(removeNode.key);
            }
        }
    }

    /// <summary>
    /// 测试LRU缓存
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("LRU缓存算法测试开始");

        // 测试用例1: 基本功能测试
        Console.WriteLine("测试用例1: 基本功能测试 (capacity=2)");
        var cache1 = new LRUCache(2);
        cache1.Put(1, 1);     // 缓存: {1=1}
        cache1.Put(2, 2);     // 缓存: {1=1, 2=2}
        Console.WriteLine($"Get(1): {cache1.Get(1)}"); // 返回1，缓存: {2=2, 1=1}
        cache1.Put(3, 3);     // 缓存满，删除最久未使用的key2，缓存: {1=1, 3=3}
        Console.WriteLine($"Get(2): {cache1.Get(2)}"); // 返回-1 (不存在)
        cache1.Put(4, 4);     // 缓存满，删除最久未使用的key1，缓存: {3=3, 4=4}
        Console.WriteLine($"Get(1): {cache1.Get(1)}"); // 返回-1 (不存在)
        Console.WriteLine($"Get(3): {cache1.Get(3)}"); // 返回3，缓存: {4=4, 3=3}
        Console.WriteLine($"Get(4): {cache1.Get(4)}"); // 返回4，缓存: {3=3, 4=4}

        // 测试用例2: 更新现有key
        Console.WriteLine("\n测试用例2: 更新现有key (capacity=1)");
        var cache2 = new LRUCache(1);
        cache2.Put(2, 1);
        Console.WriteLine($"Get(2): {cache2.Get(2)}"); // 返回1
        cache2.Put(2, 2);     // 更新key2的值
        Console.WriteLine($"Get(2): {cache2.Get(2)}"); // 返回2

        // 测试用例3: capacity=1的替换
        Console.WriteLine("\n测试用例3: capacity=1的替换");
        var cache3 = new LRUCache(1);
        cache3.Put(1, 1);
        cache3.Put(2, 2);     // 删除key1
        Console.WriteLine($"Get(1): {cache3.Get(1)}"); // 返回-1
        Console.WriteLine($"Get(2): {cache3.Get(2)}"); // 返回2

        // 测试用例4: 重复访问同一个key
        Console.WriteLine("\n测试用例4: 重复访问同一个key (capacity=2)");
        var cache4 = new LRUCache(2);
        cache4.Put(1, 1);
        cache4.Put(2, 2);
        cache4.Get(1);        // 使key1成为最近使用的
        cache4.Put(3, 3);     // 删除key2（最久未使用）
        Console.WriteLine($"Get(2): {cache4.Get(2)}"); // 返回-1
        Console.WriteLine($"Get(1): {cache4.Get(1)}"); // 返回1

        // 测试用例5: 复杂操作序列
        Console.WriteLine("\n测试用例5: 复杂操作序列 (capacity=3)");
        var cache5 = new LRUCache(3);
        cache5.Put(1, 1);
        cache5.Put(2, 2);
        cache5.Put(3, 3);
        cache5.Put(4, 4);     // 删除key1
        Console.WriteLine($"Get(4): {cache5.Get(4)}"); // 返回4
        Console.WriteLine($"Get(3): {cache5.Get(3)}"); // 返回3
        Console.WriteLine($"Get(2): {cache5.Get(2)}"); // 返回2
        Console.WriteLine($"Get(1): {cache5.Get(1)}"); // 返回-1
        cache5.Put(5, 5);     // 删除key4
        Console.WriteLine($"Get(1): {cache5.Get(1)}"); // 返回-1
        Console.WriteLine($"Get(2): {cache5.Get(2)}"); // 返回2
        Console.WriteLine($"Get(3): {cache5.Get(3)}"); // 返回3
        Console.WriteLine($"Get(4): {cache5.Get(4)}"); // 返回-1
        Console.WriteLine($"Get(5): {cache5.Get(5)}"); // 返回5

        // 测试用例6: capacity=0的边界情况
        Console.WriteLine("\n测试用例6: capacity=0的边界情况");
        var cache6 = new LRUCache(0);
        cache6.Put(1, 1);
        Console.WriteLine($"Get(1): {cache6.Get(1)}"); // 返回-1
        cache6.Put(2, 2);
        Console.WriteLine($"Get(2): {cache6.Get(2)}"); // 返回-1

        Console.WriteLine("\nLRU缓存算法测试结束");
    }
}